1. Field of the Invention
The present invention relates to generating pseudo-random digital sequences. More specifically, the present invention relates to a method and an apparatus to facilitate generating pseudo-random digital sequences that are non-periodic.
2. Related Art
Random digital sequences are useful for many purposes. Among these are statistical simulation, electronic hardware testing, communication link testing, cryptography, and the like. In practice, truly random digital sequences are difficult or nearly impossible to generate. Therefore, pseudo-random digital sequences are typically employed in place of the random digital sequences.
Pseudo-random digital sequences can be generated in many ways. Digital hardware can generate a pseudo-random digital sequence using such devices as feedback shift-registers, and many computer algorithms have been developed to generate pseudo-random numbers (digital sequences) within computer software.
Ideally, these pseudo-random digital sequence generators should not repeat the same sequence. However, since both digital hardware and computer algorithms are typically deterministic, the same sequence will eventually repeat after some finite period. Note that many techniques have been developed, both in hardware and software, to extend this period before the sequence will repeat and thus the sequence length, but nevertheless the sequence will eventually repeat.
When these pseudo-random digital sequences repeat, their usefulness for statistical simulation and testing is limited because replaying the same sequence may produce the same result as obtained previously. Additionally, a pattern that is not included in the sequence might yield new, and unexpected, results if it is included. Moreover, repeating the same pseudo-random digital sequence in a cryptographic system can present a vulnerability that can be exploited by an opponent.
What is needed is a method and an apparatus for generating pseudo-random digital sequences that does not repeat the same sequence after a finite period.
One embodiment of the present invention provides a system for generating a pseudo-random non-periodic digital sequence. The system operates by first receiving a non-periodic signal at a data input of a flip-flop. This non-periodic signal is sampled at the flip-flop with a clock signal, thereby producing the pseudo-random non-periodic digital sequence at the output of the flip-flop.
In one embodiment of the present invention, the non-periodic signal is generated by using a chaotic circuit containing three or more energy storage elements.
In one embodiment of the present invention, the chaotic circuit includes a non-linear resistance element.
In one embodiment of the present invention, the system processes the non-periodic signal from the chaotic circuit using a comparator, thereby removing an oscillating signal superimposed on the non-periodic signal.
In one embodiment of the present invention, the system samples the non-periodic signal on a rising edge of the clock signal and on a falling edge of the clock signal.
In one embodiment of the present invention, the average frequency of the non-periodic signal is greater than three times the frequency of the clock signal.
In one embodiment of the present invention, the system creates the clock signal with a programmable frequency synthesizer.
In one embodiment of the present invention, the system provides parallel pseudo-random non-periodic digital sequences originating from multiple flip-flops to a parallel-to-serial converter. This parallel-to-serial converter converts the parallel pseudo-random non-periodic digital sequences into a serial sequence at a rate that depends on the number of flip-flops. Note that the input from each flip-flop is serialized before the output of the flip-flops change. Thus, the above-described embodiment provides a second pseudo-random non-periodic digital sequence that is faster than the parallel pseudo-random non-periodic digital sequence.